package pers.vic.basics.leetcode;

import org.omg.CORBA.INTERNAL;
import org.omg.PortableInterceptor.INACTIVE;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author Vic.xu
 * @description: 85. 最大矩形  {@literal https://leetcode-cn.com/problems/maximal-rectangle/}
 * @date: 2021/2/23 0023 9:04
 */
public class J0085_H_MaximalRectangle {
    /*
    给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
     */

    /**
     * 这一题可以转化位84题的单调栈问题，
     * 把每一行作为底边，每一列连续1作为高度的柱状体的最大面积；
     */
    public static int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) {
            return 0;
        }
        int col = matrix[0].length;
        if (col == 0) {
            return 0;
        }
        if (row == 1 && col == 1) {
            return matrix[0][0] == '0' ? 0 : 1;
        }
        int area = 0;
        //每个列的高度， 前后设置个哨兵
        int[] heights = new int[col + 2];
        //以每一行为底，自上而下的连续1的数量为高的柱形最大面积
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < row; i++) {
            //计算每个柱状的高度 第一个和最后一个是哨兵
            for (int j = 0; j < col; j++) {
                heights[j + 1] = matrix[i][j] == '0' ? 0 : heights[j + 1] + 1;
            }
            //开始通过单调栈计算当前组最大面积
            area = Math.max(area, calcMaxArea(heights));
        }
        return area;

    }

    //通过单调栈计算最大面积， 当前数组已经设置哨兵
    private static int calcMaxArea(int[] heights){
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        int area = 0;
        //只要栈顶的数据大于当前数据就出栈  并计算其最大面积
        for (int i = 1; i < heights.length; i++) {
            while (heights[stack.peek()] > heights[i]) {
                int heigth = heights[stack.pop()];
                // stack.peek() 不会为空
                int width = i - stack.peek() - 1;
                area = Math.max(area, heigth * width);
            }
            stack.push(i);
        }
        return area;
    }

    public static void main(String[] args) {
        char[][] matrix = {
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'0','1','1','1','1'},
                {'1','0','1','1','0'}};
        //6
        System.out.println(maximalRectangle(matrix));

    }
}
